package fun.ticsmyc.math;

import org.junit.Test;

/**
 * @author Ticsmyc
 * @date 2020-11-25 16:01
 */
public class 快速幂 {
    long mod =1000000007; //取模
    /**
     * 思路清晰版
     * @param base
     * @param power
     * @return
     */
    public long fastPower(long base,long power){
        long result = 1;
        while(power>0){
            if(power %2 ==0){
                //指数为偶数时
                power =power /2;
                base = (base*base )%mod;
            }else{
                //指数为奇数时
                power = power-1;
                result = (result * base )%mod;
                power =power/2;
                base = (base * base)%mod;
            }
        }
        return result;
    }

    /**
     * 代码压缩版
     * @param base
     * @param power
     * @return
     */
    public long fastPower2(long base,long power){
        long result = 1;
        while(power>0){
            if( (power&1) ==1 ){
                result = (result*base)%mod;
            }
            power = power/2;
            base = (base*base )%mod;
    }
        return result;
    }

}
